/*
* @(#) TreeTraverse.java 2018年02月26日
*
* Copyright 2010 NetEase.com, Inc. All rights reserved.
*/
package com.leo.m1802.d26;

import com.sun.org.apache.bcel.internal.generic.PUSH;

import java.lang.reflect.Modifier;
import java.util.LinkedList;
import java.util.function.Consumer;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月26日
 */
public class TreeTraverse {
    Consumer consumer = new Consumer() {
        @Override public void accept(Object o) {
            System.out.print(o+" ");
        }
    };
    class Node{
        int val;
        Node left,right;
    }
    private void visitNode(Node node){
        consumer.accept(node.val);
    }

    public void preTraverse(Node node){
        if (node!=null){
            visitNode(node);
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }

    public void preTraverse1(Node node){
        LinkedList<Node> stack = new LinkedList();
        if (node!=null){ stack.push(node); }
        while (!stack.isEmpty()){
            if (node==null){ continue; }
            while (node!=null){
                visitNode(node);
                stack.push(node.right);
                node = node.left;
            }
            if (!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }

        }
    }

    public void midTraverse1(Node node){
        LinkedList<Node> stack = new LinkedList();
        if (node!=null){ stack.push(node); }
        while (!stack.isEmpty()){
            if (node==null){ continue; }
            while (node != null){
                stack.push(node);
                node=node.left;
            }
            if (!stack.isEmpty()){
                Node pop = stack.pop();
                visitNode(pop);
                node = node.right;
            }
        }
    }


    public void postTraverse1(Node node){
        LinkedList<Node> stack = new LinkedList();
        LinkedList<Node> temp = new LinkedList();
        if (node!=null) {stack.push(node);}
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            temp.push(pop);
            if (pop.left!=null){ stack.push(pop.left); }
            if (pop.right!=null){ stack.push(pop.right); }
        }
        while (!temp.isEmpty()){ visitNode(temp.pop()); }
    }

}
